#include "bt.h"

#define check_deep(top) \
	do { \
		if (top == TREE_MAX_DEPTH + 1) { \
			return ERR_STACK; \
		} \
	} while(0)

bt_node_t * bt_node_create(void)
{
	bt_node_t * node = calloc(sizeof(bt_node_t), 1);
	return node;
}

void
bt_node_release(bt_node_t * root)
{
	if (root) {
		bt_node_release(root->l_child);
		bt_node_release(root->r_child);
		free(root);
	}
}

bt_node_t *
bt_find_node(bt_node_t * root, elem_t e)
{
	bt_node_t * p = root;

	if (root) {
		if (root->data == e) {
			return root;
		}
		else if ((p = bt_find_node(root->l_child, e))) {
			return p;
		}
		else {
			return bt_find_node(root->r_child, e);
		}
	}
	else {
		return 0;
	}
}

size_t bt_height(bt_node_t * root)
{
	if (!root) {
		return 0;
	}

	size_t hl = bt_height(root->l_child) + 1;
	size_t hr = bt_height(root->r_child) + 1;

	return hl > hr ? hl : hr;
}

int
bt_r_for_each_pre_order(bt_node_t * root, bt_for_each_hook hook)
{
	int ret = 0;
	if (root) {
		if ((ret = hook(root))) {
			return ret;
		}
		if ((ret = bt_r_for_each_pre_order(root->r_child, hook))) {
			return ret;
		}
		if ((ret = bt_r_for_each_pre_order(root->l_child, hook))) {
			return ret;
		}
	}
	return ret;
}

int
bt_r_for_each_in_order(bt_node_t * root, bt_for_each_hook hook)
{
	int ret = 0;
	if (root) {
		if ((ret = bt_r_for_each_pre_order(root->r_child, hook))) {
			return ret;
		}
		if ((ret = hook(root))) {
			return ret;
		}
		if ((ret = bt_r_for_each_pre_order(root->l_child, hook))) {
			return ret;
		}
	}
	return ret;
}

int
bt_r_for_each_post_order(bt_node_t * root, bt_for_each_hook hook)
{
	int ret = 0;
	if (root) {
		if ((ret = bt_r_for_each_pre_order(root->r_child, hook))) {
			return ret;
		}
		if ((ret = bt_r_for_each_pre_order(root->l_child, hook))) {
			return ret;
		}
		if ((ret = hook(root))) {
			return ret;
		}
	}
	return ret;
}

int
bt_r_for_each_leaf(bt_node_t * root, bt_for_each_hook hook)
{
	int ret = 0;
	if (root) {
		if (root->l_child || root->r_child) {
			if (root->l_child) {
				if ((ret = bt_r_for_each_leaf(root->l_child, hook))) {
					return ret;
				}
			}
			if (root->l_child) {
				if ((ret = bt_r_for_each_leaf(root->l_child, hook))) {
					return ret;
				}
			}
			return SUCCESS;
		}
		else {
			return hook(root);
		}
	}
	else {
		return ERR_NULL_TREE;
	}
}

int
bt_r_like(bt_node_t * r0, bt_node_t * r1)
{
	if (!r0 && !r1) {
		return SUCCESS;
	}
	else if (!r0 || !r1) {
		return ERR_COMMON;
	}
	else {
		return bt_r_like(r0->l_child, r1->l_child) || bt_r_like(r0->r_child, r1->r_child);
	}
}

int
bt_r_for_each_in_path_r(bt_node_t * root, elem_t elem, bt_for_each_hook hook)
{
	if (root) {
		if (root->data == elem ||
				!bt_r_for_each_in_path_r(root->l_child, elem, hook) ||
				!bt_r_for_each_in_path_r(root->r_child, elem, hook)) {

			hook(elem);
			return 0;
		}
		else {
			return ERR_COMMON;
		}
	}
	else {
		return ERR_NULL_TREE;
	}
}

int
bt_for_each_pre_order(bt_node_t * root, bt_for_each_hook hook)
{
	if (!root) {
		return ERR_NULL_TREE;
	}

	int ret = SUCCESS;

	bt_node_t * ns[TREE_MAX_DEPTH + 2];
	bt_node_t * node = root;

	int top = 0;

	ns[++top] = node;
	while (top) {
		node = ns[top--];
		if ((ret = hook(node))) {
			return ret;
		}
		if (node->r_child) {
			ns[++top] = node->r_child;
			check_deep(top);
		}
		if (node->l_child) {
			ns[++top] = node->l_child;
			check_deep(top);
		}
	}

	return SUCCESS;
}

int
bt_for_each_in_order(bt_node_t * root, bt_for_each_hook hook)
{
	if (!root) {
		return ERR_NULL_TREE;
	}

	int ret = SUCCESS;

	bt_node_t * ns[TREE_MAX_DEPTH + 2];
	bt_node_t * node = root;

	int top = 0;

	while (top || node) {
		while (node) {
			ns[++top] = node;
			check_deep(top);
			node = node->l_child;
		}

		if (top) {
			node = ns[top--];
			if ((ret = hook(node))) {
				return ret;
			}
			node = node->r_child;
		}
	}

	return SUCCESS;
}

int bt_for_each_post_order(bt_node_t * root, bt_for_each_hook hook)
{
	// TODO

	return ERR_NOT_IMPL;
}

int
bt_for_each_post_order_x(bt_node_t * root, bt_for_each_hook hook)
{
	if (!root) {
		return ERR_NULL_TREE;
	}

	int ret = SUCCESS;

	bt_node_t * ns[TREE_MAX_DEPTH + 2];
	bt_node_t * node = root;
	bt_node_t * last = 0;

	int top = 0;

	ns[++top] = node;
	node = node->l_child;

	while (top) {

		while (node) {
			ns[++top] = node;
			node = node->l_child;
		}

		node = ns[top];

		if (last == node->r_child) {
			if ((ret = hook(node))) {
				return ret;
			}
			--top;
			last = node;
			node = 0;
		}
		else if (last == node->l_child) {
			node = node->r_child;
			last = 0;
		}
		else if (!last) {
			node = node->l_child;
			last = 0;
		}
		else {
			return ERR_COMMON;
		}
	}

	return SUCCESS;
}

int
bt_for_each_pre_order0(bt_node_t * root, bt_for_each_hook hook)
{
	// TODO

	return ERR_COMMON;
}

int
bt_for_each_in_order0(bt_node_t * root, bt_for_each_hook hook)
{
	// TODO

	return ERR_COMMON;
}

int
bt_for_each_post_order0(bt_node_t * root, bt_for_each_hook hook)
{
	// TODO

	return ERR_COMMON;
}

